#!/usr/bin/env python
# Algorithm for approximating matrix multiplication
# Cohen1999: Approximating Matrix Multiplication for Pattern Recognition Tasks
# Preprocessing
# Row scoring
import bisect as bi
import random
import numpy as np
import networkx as nx
import networkx.generators as gen
import scipy as sp
import scipy.sparse as ssp

# change to sparse matrix from networkx
# parse into compressed format 
A = [1,4,2,5]
L = [0 for x in range(len(A))]
_sum = float(sum(A))
STATS = []


#calculate probabilities 
prob = list(map((lambda x: float(x)/_sum), A))

#Calculate accumulated probability intervals
# The succession could be randomized
prob_accum = reduce((lambda result, val: (result[0] + val, result[1] + [(result[0] + val )/ _sum])), A, (0, []))[1]
print (prob_accum)
g = gen.karate_club_graph()
npm = nx.to_numpy_matrix(g)

print (ssp.issparse(g))

def sample(score):
	i = bi.bisect_left(prob_accum, score)
	L[i] = L[i] + 1
	return A[i]

for i in range (10) : 
	for x in range(1000) :
	    sample(random.random())
	# Sampled 100000 times. Add L to STATS
	STATS.append(L)
	L = [0 for x in range(len(A))] #Reset L

MAT_STATS = np.mat(STATS)
print ('probabilities of elements in A')
print (zip(A,map(lambda p: "%.4f" % p , prob)))

print ("True distribution of hitscores")
print (map(lambda x : int(100000 * x), prob))

print ("Average of samples from A")
print (np.average(MAT_STATS, axis=0))

print ("STD of samples from A")
print (np.std(MAT_STATS, axis=0, dtype=float))

print ("Min value of samples from A")
print (np.amin(MAT_STATS, axis=0))

print ("Max value of samples from A")
print (np.amax(MAT_STATS, axis=0))